class Solution {
public:
/*
//暴力遍历
    int minArray(vector<int>& numbers) {
        int min = 5000;
        for(auto i : numbers){
            if(i < min){
                min = i;
            }
        }
        return min;
    }
*/
    int TraverseArr(vector<int>& numbers, int p1, int p2) {
        int min = numbers[p1];
        for(int i = p1; i <= p2; ++i ){
            if(numbers[i] < min){
                min = numbers[i];
            }
        }
        return min;
    }

    int minArray(vector<int>& numbers) {
        int len = numbers.size();
        if(len < 2){
            return numbers[0];
        }
        
        int p1 = 0;   //前半部分翻转数字的下标
        int p2 = len - 1;  //后半部分未翻转数字的下标
        int mid = 0;
         
        //二分查找
        while(numbers[p1] >= numbers[p2]){
            //int mid = ((p2 - p1)>>1) + p1;
            mid = (p2 & p1) + ((p2 ^ p1)>>1);  //不会溢出
            if(numbers[mid] == numbers[p1] \
                  && numbers[p1] == numbers[p2]){
               //如果数值都相等遍历寻找
               return TraverseArr(numbers, p1, p2);
            }
            if(p1 + 1 == p2){
                mid = p2;  
                break;   // 满足条件
            }
            else if(numbers[mid] >= numbers[p1]){   
                // mid 下标元素位于前半部分翻转的数字
                p1 = mid;
            }
            else if(numbers[mid] <= numbers[p2]){
                // mid 下标元素位于后半部分未翻转的数字
                p2 = mid;
            }
        }
        return numbers[mid];
    }
};